// 广度优先搜索用于在非加权图中查找最短路径。
// 狄克斯特拉算法用于在加权图中查找最短路径
// 仅当权重为正时狄克斯特拉算法才管用。
// 如果图包含负权边，请使用贝尔曼-福德算法
class Graph {
    constructor() {
      this.adjacencyList = new Map(); // 初始化一个空的邻接表
    }
  
    addVertex(v) {
      if (!this.adjacencyList.has(v)) { // 如果图中还没有这个顶点
        this.adjacencyList.set(v, []); // 则添加该顶点，并初始化其邻接边列表为空数组
      }
    }
  
    addEdge(v, w, weight) {
      this.addVertex(v); // 添加顶点v
      this.addVertex(w); // 添加顶点w
      let edge = { vertex: w, weight: weight }; // 创建边的表示对象
      this.adjacencyList.get(v).push(edge); // 将边添加到顶点v的邻接边列表中
    }
  }
  
// 1、接收一个图和一个源顶点作为参数，计算从该源顶点到图中所有其他顶点的最短路径。
// 2、使用了三个对象来存储计算结果：distances存储源点到每个顶点的最短距离，previous存储最短路径上的前驱顶点，visited是一个集合，用来存储已访问过的顶点。
// 3、算法初始化所有顶点的距离为无穷大，源点的距离设为0。
// 4、然后，算法进入一个循环，每次循环中选择未访问的最小距离顶点作为当前顶点。
// 5、对于当前顶点的每一个邻接顶点，算法计算通过当前顶点到达该邻接顶点的距离，并与已知的最短距离进行比较，如果通过当前顶点的路径更短，则更新最短距离和前驱顶点。
// 当所有顶点都被访问过或者没有未访问的顶点时，算法结束。
  function dijkstra(graph, source) {
    const vertices = [...graph.adjacencyList.keys()]; // 获取图中所有顶点
    const distances = {}; // 存储源点到每个顶点的最短距离
    const previous = {}; // 存储最短路径上的前驱顶点
    const visited = new Set(); // 存储已访问过的顶点
  
    // 初始化所有顶点的距离为无穷大，除了源点
    vertices.forEach(v => {
      distances[v] = Number.POSITIVE_INFINITY;
      previous[v] = null;
    });
    distances[source] = 0;
  
    for (const vertex of vertices) {
      // 选择未访问的最小距离顶点
      let currentVertex = null;
      let minDistance = Number.POSITIVE_INFINITY;
  
      for (const v of vertices) {
        if (!visited.has(v) && distances[v] <= minDistance) { 
          currentVertex = v;
          minDistance = distances[v];
        }
      }
  
      // 如果所有顶点都被访问过，或者没有找到未访问的顶点，则结束
      if (currentVertex === null) break;
  
      visited.add(currentVertex); // 标记当前顶点为已访问
  
      // 更新邻接顶点的距离
      for (const edge of graph.adjacencyList.get(currentVertex)) {
        const targetVertex = edge.vertex;
        const weight = edge.weight;
        const newDistance = distances[currentVertex] + weight;
  
        if (newDistance < distances[targetVertex]) {
          distances[targetVertex] = newDistance; // 更新距离
          previous[targetVertex] = currentVertex; // 更新前驱顶点
        }
      }
    }
  
    return { distances, previous }; // 返回计算结果
  }
  
  // 示例图
  const graph = new Graph();
  graph.addEdge(0, 1, 5);
  graph.addEdge(0, 2, 2);
  graph.addEdge(1, 3, 4);
  graph.addEdge(1, 4, 4);
  graph.addEdge(2, 5, 7);
  graph.addEdge(3, 4, 1);
  graph.addEdge(4, 5, 1);
  console.log('邻接表:', graph.adjacencyList);
  
  // 计算从顶点0到所有其他顶点的最短路径
  const { distances, previous } = dijkstra(graph, 0);
  
  console.log('距顶点 0 的距离:', distances);
  console.log('前驱顶点在最短路径上的顶点:', previous);

  
module.exports = Graph